﻿//给定两个长度相等的数组 nums1 和 nums2，
//nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
//返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
//
//输入：nums1 = [2, 7, 11, 15], nums2 = [1, 10, 4, 11]
//输出：[2, 11, 7, 15]
//
//输入：nums1 = [12, 24, 8, 32], nums2 = [13, 25, 32, 11]
//输出：[24, 32, 8, 12]
//
//提示：
//	1 <= nums1.length <= 10^5
//	nums2.length == nums1.length
//	0 <= nums1[i], nums2[i] <= 10^9

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        // 1.排序

        sort(nums1.begin(), nums1.end());
        vector<int> index2(n);
        for (int i = 0; i < n; i++)
            index2[i] = i;
        sort(index2.begin(), index2.end(),
            [&](int i, int j) { return nums2[i] < nums2[j]; });
        // 2.⽥忌赛⻢

        vector<int> ret(n);
        int left = 0, right = n - 1;
        for (auto x : nums1) {
            if (x > nums2[index2[left]])
                ret[index2[left++]] = x;
            else
                ret[index2[right--]] = x;
        }
        return ret;
    }
};